home *** CD-ROM | disk | FTP | other *** search
/ STraTOS 1997 April & May / STraTOS 1 - 1997 April & May.iso / CD01 / PRGMANIA / QEDSRC / MEMORY.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-12-29  |  13.7 KB  |  636 lines
  1. /*
  2.  
  3. Ja, Du hast Recht. Einmal allozierter Speicher wird nicht wieder
  4. freigegeben. Das hat mich auch schon immer gestoert, ich hatte aber
  5. nie die Zeit daran mal was zu aendern.
  6. QED holt sich vom System immer Bloecke einer bestimmten Groesse und
  7. verwaltet sie dann selbst. Eine richtige garbage collection findet
  8. nicht statt. Werden aber zwei Zeilen, die im Speicher hintereinander
  9. gelegen haben wieder frei gegeben, werden sie wieder zu einem grossen
  10. Block verschmolzen. Das erfolgt sehr effizient (und damit ist der Code
  11. ziemlich grausam).
  12. Alle freien Bloecke einer Groesse werden in einer verketteten Liste
  13. gehalten. Die Anfaenge dieser Listen stehen in einem Array. Um bei der
  14. freigabe einer Zeile aber nun schnell festzustennen, ob dahinter noch
  15. ein anderer freier Block ist (und nicht erst alle Listen durchlaufen
  16. zu muessen), mit dem der erste dann verschmolzen
  17. werden kann, gibt es dieses MAGIC-Word. Ich sehe also direkt im
  18. Speicher hinter dem ersten Block nach, ob dort das Magic-Word
  19. steht. Wenn ja, dann liegt dort ein freier Block. Damit ich weiss um
  20. einen Block welcher Groesse es sich handelt, steht dort auch noch die
  21. Groessse und fuer eine einfache Umhaengung in den Listen auch gleich die
  22. Zeiger auf Vorgaenger und Nachfolger in der Liste.
  23. Lange Rede, kurzen Sinn: mit diesem Verfahren ist es moeglich in
  24. *konstanter* Zeit eine Free-Operation mit Verschmelzung zu
  25. realisieren.
  26. Aber daran brauchst Du wohl garnichts aendern, wenn Du das Programm so
  27. verbessern willst, dass es den Speicher ans System wieder
  28. zurueckgibt. Du musst nur ueberpruefen, ob ein Block komplett frei
  29. ist. Wenn das der Fall ist, musst Du alle kleinen Bloecke aus den
  30. free_list-Listen herausnehemen und kannst dann den Block ans System
  31. zureuckgeben.
  32.  
  33. */
  34.  
  35. #include "global.h"
  36. #include "qed.h"
  37. #include "text.h"
  38. #include "windows.h"
  39. #include "scroll.h"
  40.  
  41. #undef MAGIC
  42. #define MAGIC            0xFED1
  43. #define MAX_ANZ        67
  44. #define BLOCK_SIZE    (MAX_ANZ*4)
  45. #define BLOCKANZ        200                                    /* Für einen malloc */
  46. #define MEMSIZE        ((LONG)BLOCK_SIZE*BLOCKANZ)    /* für einen malloc */
  47.  
  48. #define MEM_SIZE(x)    (((x)+2+3)&(~3))                        /* 2 Bytes drauf für den Kopf */
  49. #define MEM_ADD(x,d)    (BLOCK*)((char*)(x)+(d))
  50. #define MEM_SUB(x,d)    (BLOCK*)((char*)(x)-(d))
  51.  
  52. typedef union tblock{
  53.                         struct{
  54.                                 UWORD magic;        /* 2 Bytes */
  55.                                 UWORD size;        /* 2 Bytes */
  56.                                 union tblock *next;        /* 4 Bytes */
  57.                                 union tblock *prev;        /* 4 Bytes => 12 Bytes */
  58.                                 }FREI;
  59.                         struct{
  60.                                 UWORD size;        /* 2 Bytes */
  61.                                 }USED;
  62.                             } BLOCK;
  63.  
  64. LOCAL BOOLEAN    mem_need_BS,                    /* BS hat keinen Speicher mehr */
  65.                     mem_need_TQ;                    /* TQ hat keinen Speicher mehr */
  66. LOCAL VOID*        block_list;
  67. LOCAL BLOCK*    free_list[MAX_ANZ+1+1];        /* ein Dummy am Ende */
  68.  
  69.  
  70.  
  71. LOCAL VOID new_block(VOID)
  72. {
  73.     BLOCK *adr, *adr2, *pre;
  74.     LONG  *ptr;
  75.     LONG    anz, i;
  76.  
  77.     anz = (LONG)Malloc(-1L);
  78.     if (anz>=4+MEMSIZE+4)
  79.     {
  80.         ptr = (LONG*)Malloc(4+MEMSIZE+4);
  81.         anz -= 4+MEMSIZE+4;
  82.     }
  83.     else
  84.         ptr = NULL;
  85.     if (anz < MEMSIZE+20000L)
  86.         mem_need_BS = TRUE;
  87.     if (ptr == NULL)
  88.     {
  89.         if (anz>=4+BLOCK_SIZE+4)
  90.         {
  91.             i = anz = (anz-8)/(BLOCK_SIZE);
  92.             anz = 4+(anz*BLOCK_SIZE)+4;
  93.             ptr = (LONG*)Malloc(anz);
  94.         }
  95.         else
  96.         {
  97.             note(1, FATALMEM);
  98.             Pterm(1);
  99.         }
  100.         mem_need_TQ = TRUE;
  101.     }
  102.     else
  103.     {
  104.         i = BLOCKANZ;
  105.         mem_need_TQ = FALSE;
  106.     }
  107.  
  108.     *(VOID**)ptr = block_list;            /* In Liste einhängen */
  109.     block_list = ptr;
  110.     adr = MEM_ADD(ptr,4);
  111.  
  112.     free_list[MAX_ANZ] = adr;
  113.     pre = NULL;
  114.     while ((--i)>0)
  115.     {
  116.         adr2 = MEM_ADD(adr,BLOCK_SIZE);
  117.         *(LONG*)&adr->FREI.magic = (LONG)(MAGIC<<16)+BLOCK_SIZE;
  118.                                             /*    adr->FREI.magic = MAGIC;        */
  119.                                             /*    adr->FREI.size = BLOCK_SIZE;    */
  120.         adr->FREI.next = adr2;
  121.         adr->FREI.prev = pre;
  122.         pre = adr;
  123.         adr = adr2;
  124.     }
  125.     adr2 = MEM_ADD(adr,BLOCK_SIZE);
  126.     *(LONG*)&adr->FREI.magic = (LONG)(MAGIC<<16)+BLOCK_SIZE;
  127.                                         /*    adr->FREI.magic = MAGIC;        */
  128.                                         /*    adr->FREI.size = BLOCK_SIZE;    */
  129.     adr->FREI.next = NULL;
  130.     adr->FREI.prev = pre;
  131.  
  132.     *(LONG*)adr2 = 0L;            /* damit bei FREE da kein MAGIC steht */
  133. }
  134.  
  135. LOCAL VOID *MALLOC(UWORD size)
  136. {
  137.     BLOCK *adr, **feld;
  138.  
  139.     size = MEM_SIZE(size);
  140.     if (size>BLOCK_SIZE)
  141.     {
  142.         inote(1, FATALERR, 5);
  143.         size = BLOCK_SIZE;
  144.     }
  145.     feld = (BLOCK**)((char*)free_list+size);
  146.     if (*feld==NULL)                                                /* kein passender */
  147.     {
  148.         if (size+16<=BLOCK_SIZE)                    /* grö₧eren Block suchen und teilen */
  149.         {
  150.             BLOCK *adr2;
  151.             WORD    i;
  152.  
  153.             i = size+16; feld += 4;                /* 16 Bytes kleinster Block zum Abspalten */
  154.             while (TRUE)                                            /* grö₧eren Block suchen */
  155.             {
  156.                 if (*feld++!=NULL) break; i+=4;
  157.                 if (*feld++!=NULL) break; i+=4;
  158.                 if (*feld++!=NULL) break; i+=4;
  159.                 if (*feld++!=NULL) break; i+=4;
  160.                 if (*feld++!=NULL) break; i+=4;
  161.                 if (*feld++!=NULL) break; i+=4;
  162.                 if (*feld++!=NULL) break; i+=4;
  163.                 if (*feld++!=NULL) break; i+=4;
  164.             }
  165.             feld--;
  166.             if (i==(BLOCK_SIZE+4))                                /* kein Block vorhanden */
  167.             {
  168.                 new_block();
  169.                 feld--; i-=4;
  170.             }
  171.             adr = *feld;                                            /* Zeiger auf Block */
  172.             *feld = adr->FREI.next;                                /* Aushängen */
  173.             if (*feld!=NULL) (*feld)->FREI.prev = NULL;
  174.             adr->USED.size = size;
  175.  
  176.             /* Rest in die free_list einhängen */
  177.             adr2 = MEM_ADD(adr,size);                                /* Zeiger auf Restblock */
  178.             (char*)feld -= size;
  179.             i -= size;                                                /* Restgrö₧e */
  180.             adr2->FREI.magic = MAGIC;                            /* Einhängen */
  181.             adr2->FREI.size = i;
  182.             adr2->FREI.next = *feld;
  183.             adr2->FREI.prev = NULL;
  184.             if (*feld!=NULL) (*feld)->FREI.prev = adr2;
  185.             *feld = adr2;
  186.         }
  187.         else                                                            /* grö₧ten Block nehmen */
  188.         {
  189.             feld = (BLOCK**)(&free_list[MAX_ANZ]);
  190.             if (*feld==NULL)                                        /* kein Block vorhanden */
  191.                 new_block();
  192.             adr = *feld;                                            /* Zeiger auf Block */
  193.             *feld = adr->FREI.next;                                /* Aushängen */
  194.             if (*feld!=NULL) (*feld)->FREI.prev = NULL;
  195.             adr->USED.size = BLOCK_SIZE;
  196.         }
  197.     }
  198.     else                                                                /* passend vorhanden */
  199.     {
  200.         adr = *feld;                                                /* Zeiger auf Block */
  201.         *feld = adr->FREI.next;                                    /* Aushängen */
  202.         if (*feld!=NULL) (*feld)->FREI.prev = NULL;
  203.         adr->USED.size = size;
  204.     }
  205.     if (free_list[MAX_ANZ]==NULL)
  206.         mem_need_TQ = TRUE;
  207.     return(MEM_ADD(adr,2));
  208. }
  209.  
  210. LOCAL VOID FREE(VOID *adr)
  211. {
  212.     WORD    size1, size2;
  213.     BLOCK *adr1, *adr2, **feld;
  214.  
  215.     adr1 = MEM_SUB(adr,2);                                            /* adr1 auf ersten Block */
  216.     size1 = adr1->USED.size;
  217. /*#ifdef CONCAT*/
  218.     adr2 = MEM_ADD(adr1,size1);                                        /* adr2 auf Nachfolger */
  219.     size2 = adr2->FREI.size;
  220.     if (adr2->FREI.magic==MAGIC && (size1+size2<=BLOCK_SIZE))
  221.     /* freier Block dahinter => Zusammenfügen */
  222.     {
  223.         BLOCK    *pre;
  224.  
  225.         pre = adr2->FREI.prev;                                    /* Aushängen */
  226.         if (pre==NULL)                                                /* erster in der Liste */
  227.             *(BLOCK**)((char*)free_list+size2) = adr2->FREI.next;
  228.         else
  229.             pre->FREI.next = adr2->FREI.next;
  230.         if (adr2->FREI.next!=NULL)                                /* es gibt Nachfolger */
  231.             adr2->FREI.next->FREI.prev = pre;
  232.         size1 += size2;
  233.     }
  234. /*#endif*/
  235.     feld = (BLOCK**)((char*)free_list+size1);                /* Einhängen */
  236.     adr1->FREI.magic = MAGIC;
  237.     adr1->FREI.size = size1;
  238.     adr1->FREI.next = *feld;
  239.     adr1->FREI.prev = NULL;
  240.     if (*feld!=NULL) (*feld)->FREI.prev = adr1;
  241.     *feld = adr1;
  242.  
  243.     if (size1==BLOCK_SIZE)
  244.         mem_need_TQ = FALSE;
  245. }
  246.  
  247. /* =========================================================== */
  248.  
  249. VOID INSERT(LINEP *a, WORD pos, WORD delta, const char *str)
  250. {
  251.     COPYB(REALLOC(a,pos,delta),str,delta);
  252. }
  253.  
  254. /* =========================================================== */
  255.  
  256. char *REALLOC(LINEP *a, WORD pos, WORD delta)
  257. {
  258.     LINEP    col;
  259.     WORD    new_len;
  260.     BLOCK *adr;
  261.  
  262.     col = *a;
  263.     if (delta==0) return(TEXT(col)+pos);
  264.  
  265.     new_len = col->len+delta;
  266.     if (new_len<0 || new_len>MAX_LINE_LEN)
  267.         note(1, FATALMEM);
  268.     adr = MEM_SUB(col,2);
  269.     if (MEM_SIZE((UWORD)sizeof(ZEILE)+new_len+1) != adr->USED.size)
  270.     {
  271.         LINEP    new;
  272.  
  273.         new = MALLOC( (short) sizeof(ZEILE) + new_len + 1);
  274.         COPYW(new, col, (short) sizeof(ZEILE)+pos);
  275.         if (delta<0)
  276.         {
  277.             new->len = new_len;
  278.             COPYB(TEXT(new)+pos,TEXT(col)+pos-delta,new_len-pos+1);
  279.         }
  280.         else
  281.         {
  282.             COPYB(TEXT(new)+pos+delta,TEXT(col)+pos,col->len-pos+1);
  283.             new->len = new_len;
  284.         }
  285.         FREE(col);
  286.         new->vorg->nachf = new;
  287.         new->nachf->vorg = new;
  288.         *a = new;
  289.         return(TEXT(new)+pos);
  290.     }
  291.     else    /* Der Platzt in der Zeile reicht */
  292.     {
  293.         if (delta<0)
  294.         {
  295.             col->len = new_len;
  296.             COPYB(TEXT(col)+pos,TEXT(col)+pos-delta,new_len-pos+1);
  297.         }
  298.         else
  299.         {
  300.             MOVE(TEXT(col)+pos+delta,TEXT(col)+pos,col->len-pos+1);
  301.             col->len = new_len;
  302.         }
  303.         return(TEXT(col)+pos);
  304.     }
  305. }
  306.  
  307. LINEP new_col_w(const char *str, WORD l)
  308. {
  309.     LINEP a;
  310.  
  311.     a = (LINEP)MALLOC( (short) sizeof(ZEILE)+l+1);
  312.     a->info = 0;
  313.     a->len = l;
  314.     COPYW(TEXT(a),str,l);
  315.     TEXT(a)[l] = EOS;
  316.     return(a);
  317. }
  318.  
  319. LINEP new_col_b(const char *str, WORD l)
  320. {
  321.     LINEP a;
  322.  
  323.     a = (LINEP)MALLOC( (short)sizeof(ZEILE)+l+1);
  324.     a->info = 0;
  325.     a->len = l;
  326.     if ((WORD)str&1)
  327.     {
  328.         *(char*)COPYB(TEXT(a),str,l) = EOS;
  329.     }
  330.     else
  331.     {
  332.         COPYW(TEXT(a),str,l);
  333.         TEXT(a)[l] = EOS;
  334.     }
  335.     return(a);
  336. }
  337.  
  338. VOID free_col(LINEP col)
  339. {
  340.     FREE(col);
  341. }
  342.  
  343. /* Zeile nach WO einfügen      */
  344. LINEP col_insert(LINEP wo, LINEP was)
  345. {
  346.     LINEP help;
  347.  
  348.     help = wo->nachf;
  349.     help->vorg = was;
  350.     was->nachf = help;
  351.     was->vorg = wo;
  352.     wo->nachf = was;
  353.     return was;
  354. }
  355.  
  356. /* Zeile am Ende anhängen */
  357. VOID col_append(RINGP t, LINEP was)
  358. {
  359.     LINEP help;
  360.  
  361.     help = LAST(t);
  362.     was->vorg = help;
  363.     was->nachf = help->nachf;
  364.     help->nachf = was;
  365.     t->tail.vorg = was;
  366.     t->lines++;
  367. }
  368.  
  369. VOID col_delete(LINEP wo)
  370. {
  371.     wo->vorg->nachf = wo->nachf;
  372.     wo->nachf->vorg = wo->vorg;
  373.     FREE(wo);
  374. }
  375.  
  376. VOID col_concate(LINEP *wo)
  377. {
  378.     LINEP        help, col;
  379.     BOOLEAN    absatz;
  380.  
  381.     col = *wo;
  382.     help = col->nachf;
  383.     if (col->len)
  384.     {
  385.         absatz = help->info&ABSATZ;
  386.         INSERT(&col, col->len, help->len, TEXT(help));
  387.         help->nachf->vorg = col;
  388.         col->nachf = help->nachf;
  389.         FREE(help);
  390.         if (absatz)
  391.             col->info |= ABSATZ;
  392.         else
  393.             col->info &= ~ABSATZ;
  394.         *wo = col;
  395.     }
  396.     else
  397.     {
  398.         col->vorg->nachf = help;
  399.         help->vorg = col->vorg;
  400.         FREE(col);
  401.         *wo = help;
  402.     }
  403. }
  404.  
  405. VOID col_split(LINEP *col,WORD pos)
  406. {
  407.     LINEP        new,help;
  408.     WORD        anz;
  409.     BOOLEAN    absatz;
  410.  
  411.     help = *col;
  412.     absatz = help->info&ABSATZ;
  413.     help->info &= ~ABSATZ;
  414.     if (pos==0)
  415.     {
  416.         new = new_col_w ("",0);
  417.         col_insert(help->vorg,new);
  418.         *col = new;
  419.     }
  420.     else if (pos<help->len)
  421.     {
  422.         anz = help->len-pos;
  423.         new = new_col_b (TEXT(help)+pos, anz);
  424.         col_insert (help, new);
  425.         REALLOC(&help,pos,-anz);
  426.         *col = help;
  427.     }
  428.     else
  429.     {
  430.         new = new_col_w ("",0);
  431.         col_insert(help,new);
  432.     }
  433.     if (absatz) (*col)->nachf->info |= ABSATZ;
  434.     else (*col)->nachf->info &= ~ABSATZ;
  435. }
  436.  
  437. LINEP get_line(RINGP r, LONG y)
  438. {
  439.     LINEP    lauf;
  440.  
  441.     if (y<0 || y>=r->lines) return NULL;
  442.     if (y<(r->lines>>1))
  443.     {
  444.         lauf = FIRST(r);
  445.         while ((--y)>=0) NEXT(lauf);
  446.     }
  447.     else
  448.     {
  449.         lauf = LAST(r);
  450.         y = r->lines-y;
  451.         while ((--y)>0) VORG(lauf);
  452.     }
  453.     return lauf;
  454. }
  455.  
  456. /*=========================================================================*/
  457.  
  458. VOID init_textring(RINGP r)
  459. {
  460.     LINEP    a;
  461.  
  462.     r->head.info = HEAD;
  463.     r->tail.info = TAIL;
  464.     a = new_col_w("",0);
  465.     a->nachf = &r->tail;
  466.     a->vorg = &r->head;
  467.     LAST(r) = a;
  468.     r->tail.nachf = NULL;
  469.     FIRST(r) = a;
  470.     r->head.vorg = NULL;
  471.     r->lines = 1;
  472.     r->longest_len = 0;
  473. }
  474.  
  475. LONG textring_bytes(RINGP r, LineEnding ending)
  476. {
  477.     LINEP    lauf, ende;
  478.     LONG    bytes;
  479.  
  480.     lauf = FIRST(r);
  481.     ende = LAST(r);
  482.     bytes = lauf->len;
  483.     while(lauf!=ende)
  484.     {
  485.         NEXT(lauf);
  486.         bytes += lauf->len;
  487.     }
  488.     /* plus Zeilenenden: 1 Zeichen für alle */
  489.     bytes += r->lines-1;
  490.     if (ending == tos)
  491.         /* für TOS noch ein Zeichen */
  492.         bytes += r->lines-1;
  493.     return bytes;
  494. }
  495.  
  496.  
  497. WORD get_longest_len(RINGP r)
  498. {
  499. /*
  500.     WORD    max;
  501.     LINEP lauf;
  502.  
  503.     max = 0;
  504.     lauf = FIRST(r);
  505.     if (lauf != NULL)
  506.     {
  507.         while (!IS_LAST(lauf))
  508.         {
  509.             if (lauf->len > max)
  510.                 max = lauf->len;
  511.             NEXT(lauf);
  512.         }
  513.         r->longest_len = max;
  514.     }
  515.     return max;
  516. */
  517.     return 0;
  518. }
  519.  
  520. VOID free_textring(RINGP r)
  521. {
  522.     LINEP lauf, frei, ende;
  523.  
  524.     frei = LAST(r);                /* letzte Zeile */
  525.     lauf = frei->vorg;            /* vorletzte Zeile */
  526.     ende = FIRST(r);                /* erste Zeile */
  527.     while (frei!=ende)
  528.     {
  529.         FREE(frei);
  530.         frei = lauf;
  531.         VORG(lauf);
  532.     }
  533.     LAST(r) = frei;
  534.     frei->nachf = &r->tail;
  535.     REALLOC(&frei,0,-(frei->len));
  536.     frei->info = 0;
  537.     r->lines = 1;
  538. }
  539.  
  540. VOID kill_textring(RINGP r)
  541. {
  542.     free_textring(r);
  543.     FREE(FIRST(r));
  544.     FIRST(r) = NULL;
  545.     LAST(r) = NULL;
  546.     r->lines = 0;
  547. }
  548.  
  549. BOOLEAN doppeln(RINGP old, RINGP new)
  550. {
  551.     LINEP        lauf, neu, a;
  552.     LONG        lines, anz;
  553.     BOOLEAN    erg;
  554.  
  555.     erg = TRUE;
  556.     free_textring(new);
  557.     a      = FIRST(new);
  558.     lauf = FIRST(old);
  559.     anz    = old->lines;
  560.  
  561.     INSERT(&a, 0, lauf->len, TEXT(lauf));
  562.     a->info = lauf->info;
  563.     NEXT(lauf);
  564.     NEXT(a);
  565.     lines = 1L;
  566.     while (lines<anz)
  567.     {
  568.         neu = new_col_w(TEXT(lauf),lauf->len);
  569.         neu->info = lauf->info;                        /* ABSATZ mit kopieren */
  570.         col_insert(a->vorg,neu);
  571.         NEXT(lauf);
  572.         lines++;
  573.         if (!ist_mem_frei())
  574.         {
  575.             erg = FALSE;
  576.             break;
  577.         }
  578.     }
  579.     new->lines = lines;
  580.     return erg;
  581. }
  582.  
  583. BOOLEAN ist_leer(RINGP r)
  584. {
  585.     return(r->lines==1 && FIRST(r)->len==0);
  586. }
  587.  
  588. /*=========================================================================*/
  589.  
  590. VOID kill_memory(VOID)
  591. {
  592.     WORD    i;
  593.     BLOCK **ptr;
  594.     VOID    *help;
  595.  
  596.     for (i=MAX_ANZ+1,ptr=free_list; (--i)>=0; )
  597.     {
  598.         *ptr++ = NULL;
  599.     }
  600.     while (block_list!=NULL)
  601.     {
  602.         help = *(VOID**)block_list;        /* nächster Block */
  603.         Mfree(block_list);
  604.         block_list = help;
  605.     }
  606.     mem_need_TQ = mem_need_BS = FALSE;
  607. }
  608.  
  609. BOOLEAN is_mem_free(VOID)
  610. {
  611.     return (!(mem_need_BS && mem_need_TQ));
  612. }
  613.  
  614. BOOLEAN ist_mem_frei(VOID)
  615. {
  616.     if (mem_need_BS && mem_need_TQ)
  617.     {
  618.         note(1,NOMEMORY);
  619.         return (FALSE);
  620.     }
  621.     else
  622.         return (TRUE);
  623. }
  624.  
  625. VOID init_memory(VOID)
  626. {
  627.     WORD    i;
  628.     BLOCK **ptr;
  629.  
  630.     mem_need_TQ = mem_need_BS = FALSE;
  631.     for (i=MAX_ANZ+1,ptr=free_list; (--i)>=0; )
  632.         *ptr++ = NULL;
  633.     *ptr = (VOID*)-1L;    /* für schleifenende */
  634.     block_list = NULL;
  635. }
  636.